//    010. 质数的和
//    10 以下的质数的和为 2+3+5+7=17，求所有两百万以下的质数的和。
//    答案：142913828922
//    欧拉筛素数( O(n) )
//    埃氏筛素数( O(nlog(n)) )

import java.util.GregorianCalendar;


public class week010 {

    /*
     *@ prime[i] :第i个素数
     *@ mv[i]    :i的最小质因子
     *@ 质数的最小质因子为它本身
     *@ 请不要更改传入的数组的值（即全为0）
     */
    // 欧拉筛1~n的素数
    public static int GetPrime(int[] prime, int[] mv, int n) {
        int tot = 0;
        for (int i = 2; i <= n; ++i) {
            if (mv[i] == 0) {
                prime[tot++] = i;
                mv[i] = i;
            }
            for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
                mv[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
        return tot;
    }

    public static void main(String[] args) {
        int n = 2000000;
        int[] prime = new int[n], mv = new int[n + 1];
        int tot = GetPrime(prime, mv, n);
        long sum = 0;
        for (int i = 0; i < tot; ++i) sum += prime[i];
        System.out.println(sum);
    }
}

